package 力扣.动态规划;

public class 按摩师 {
    public static void main(String[] args) {
        int[] nums={1,2,3,1};
        int massage = massage(nums);
        System.out.println(massage);
    }
    public static int massage(int[] nums) {
        int n=nums.length;
        if(n==0)
            return 0;
        //nums[i]结尾的最大值
        int[] dp = new int[n+1];
        //初始化
        dp[1]=nums[0];
        int res=0;
        for (int i = 2; i < n+1; i++) {
            for (int j = 0; j < i - 1; j++) {
                dp[i]=Math.max(dp[i],dp[j]+nums[i-1]);
            }
            res=Math.max(dp[i],res);
        }
        return res>nums[0]?res:nums[0];
    }
}
